package com.misakora.utilpackage.datastruct.sort;

import com.misakora.designpatterns.strategy.AnimalComparator;
import com.misakora.designpatterns.strategy.Cat;

public class  SortUtil <T>{


    /**
     * 堆排序
     *
     */



    /**
     * 选择排序
     * @param arr
     */
    public void selectSort(int[] arr){

    }


    /**
     * 冒泡排序
     * @param arr
     */
    public void bubbleSort(int[] arr){
        int len = arr.length-1;
        for (int i = 0; i < arr.length-1; i++) {
            for (int j = 0; j < len; j++) {
                if (arr[j]> arr[j+1]){
                    swap(arr,j,j+1);
                }
            }
            len--;
        }
    }

    /**
     * 交换两个索引处的元素
     * @param arr 数组
     * @param i i
     * @param j j
     */
    private void swap(int[] arr, int i, int j) {
        arr[i] ^= arr[j];
        arr[j] ^= arr[i];
        arr[i] ^= arr[j];
    }

    /**
     * 快速排序算法的入口
     * @param arr 数组
     */
    public void quickSort(int[] arr){
        quickSort(arr,0, arr.length-1);
    }
    /**
     * 快速排序 本体
     * @param arr  数组
     * @param low
     * @param high
     */
    private void quickSort(int[] arr ,int low ,int high){
        if (low>=high){
            return;
        }
        int i=low,j=high,
                temp = arr[low];//哨兵
        while(i<j){
            while(arr[j]>=temp && i<j){ // 先移动右边的j ;
                j--;
            }
            while(arr[i]<=temp && i<j){  //再移动左边的i
                i++;
            }
            if (i<j){
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
        //最后将 i和j相等的位置上的数和基准哨兵交换
        arr[low] = arr[i];
        arr[i] = temp;

        quickSort(arr,low,i-1);
        quickSort(arr, j+1,high);

    }

    /**
     * 快速排序算法的入口
     * @param arr 数组
     */
    public void quickSort(Comparable[] arr){
        quickSort(arr,0, arr.length-1);
    }
    /**
     * 快速排序 本体
     * @param arr  数组
     * @param low
     * @param high
     */
    private void quickSort(Comparable[] arr , int low , int high){
        if (low>=high){
            return;
        }
        int i=low,j=high;
        Comparable temp = arr[low];//哨兵
        while(i<j){
            while(arr[j].compareTo(temp)==-1 ? false : true  && i<j){ // 先移动右边的j ;
                j--;
            }
            while(arr[i].compareTo(temp)==1 ? false : true && i<j){  //再移动左边的i
                i++;
            }
            if (i<j){
                Comparable t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
        //最后将 i和j相等的位置上的数和基准哨兵交换
        arr[low] = arr[i];
        arr[i] = temp;

        quickSort(arr,low,i-1);
        quickSort(arr, j+1,high);

    }

    public void quickSort(T[] catArr, AnimalComparator<T> catAnimalComparator) {
        quickSort(catArr,0, catArr.length-1,catAnimalComparator);
    }
    /**
     * 快速排序 本体
     * @param catArr  数组
     * @param low
     * @param high
     * @param catAnimalComparator  比较策略
     */
    private void quickSort(T[] catArr, int low, int high, AnimalComparator<T> catAnimalComparator) {

        if (low>=high){
            return;
        }
        int i=low,j=high;
        T temp = catArr[low];//哨兵
        while(i<j){
            while(catAnimalComparator.compare(catArr[j],temp) == -1 ? false : true  && i<j){ // 先移动右边的j ;
                j--;
            }
            while(catAnimalComparator.compare(catArr[i],temp) == 1 ? false : true && i<j){  //再移动左边的i
                i++;
            }
            if (i<j){
                T t = catArr[i];
                catArr[i] = catArr[j];
                catArr[j] = t;
            }
        }
        //最后将 i和j相等的位置上的数和基准哨兵交换
        catArr[low] = catArr[i];
        catArr[i] = temp;

        quickSort(catArr,low,i-1,catAnimalComparator);
        quickSort(catArr, j+1,high,catAnimalComparator);

    }
}
